{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Multiply Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: multiply"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串相乘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个以字符串形式表示的非负整数&nbsp;<code>num1</code>&nbsp;和&nbsp;<code>num2</code>，返回&nbsp;<code>num1</code>&nbsp;和&nbsp;<code>num2</code>&nbsp;的乘积，它们的乘积也表示为字符串形式。</p>\n",
    "\n",
    "<p><strong>注意：</strong>不能使用任何内置的 BigInteger 库或直接将输入转换为整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num1 = \"2\", num2 = \"3\"\n",
    "<strong>输出:</strong> \"6\"</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> num1 = \"123\", num2 = \"456\"\n",
    "<strong>输出:</strong> \"56088\"</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num1.length, num2.length &lt;= 200</code></li>\n",
    "\t<li><code>num1</code>&nbsp;和 <code>num2</code>&nbsp;只能由数字组成。</li>\n",
    "\t<li><code>num1</code>&nbsp;和 <code>num2</code>&nbsp;都不包含任何前导零，除了数字0本身。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [multiply-strings](https://leetcode.cn/problems/multiply-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [multiply-strings](https://leetcode.cn/problems/multiply-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"2\"\\n\"3\"', '\"123\"\\n\"456\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "        \n",
    "        m, n = len(num1), len(num2)\n",
    "        res = [0]*(m+n)\n",
    "        \n",
    "        num1 = num1[::-1]\n",
    "        num2 = num2[::-1]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a, b = int(num1[i]), int(num2[j])\n",
    "                res[i+j] += a*b\n",
    "                res[i+j+1] += res[i+j]//10\n",
    "                res[i+j] = res[i+j]%10\n",
    "        \n",
    "        if res[-1] == 0:\n",
    "            res.pop()\n",
    "            \n",
    "        return ''.join(str(r) for r in reversed(res))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: 'str', num2: 'str') -> 'str':\n",
    "        ret = [0] * 12100\n",
    "        n1 = list(map(int, num1))[::-1] + [0]\n",
    "        n2 = list(map(int, num2))[::-1] + [0]\n",
    "\n",
    "        # print(n1, n2)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(n1):\n",
    "            j = 0\n",
    "            carry_p = 0\n",
    "            carry_m = 0\n",
    "            while j < len(n2):\n",
    "                v = n2[j] * n1[i] + carry_m\n",
    "                carry_m = v // 10\n",
    "                v = v % 10\n",
    "                carry_p, v = (v + carry_p + ret[i + j]) // 10, (v + carry_p + ret[i + j]) % 10\n",
    "                ret[i + j] = v\n",
    "                # print(ret)\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        s = ''\n",
    "        i, j = 0, len(ret) - 1\n",
    "        while j >= 0 and ret[j] == 0:\n",
    "            j -= 1\n",
    "        for i in range(j + 1):\n",
    "            s = str(ret[i]) + s\n",
    "\n",
    "        if s:\n",
    "            return s\n",
    "        else:\n",
    "            return '0'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        output = \"\"\n",
    "\n",
    "        for i in range(len(num2)-1,-1,-1):\n",
    "            num = 0\n",
    "            rest = 0\n",
    "            temp = \"\"\n",
    "            for j in range(len(num1)-1,-1, -1):\n",
    "                num = int((int(num2[i]) * int(num1[j])+rest) % 10)\n",
    "                rest = int((int(num2[i]) * int(num1[j])+rest) /10)\n",
    "                temp = str(num) + temp\n",
    "            for index in range(len(num2)-1-i):\n",
    "                temp += \"0\"\n",
    "            # print(output, temp)\n",
    "            if rest != 0:\n",
    "                temp = str(rest) + temp\n",
    "            # print(\"the i is:\", temp, output)\n",
    "            output = self.add2Num(output, temp)\n",
    "            # print(output)\n",
    "        while output[0] == \"0\" and len(output) > 1:\n",
    "            output = output[1:]\n",
    "        return output\n",
    "            \n",
    "            \n",
    "    def add2Num(self, num1, num2, rest = 0):\n",
    "        if num1 == \"\":\n",
    "            if rest == 0:\n",
    "                return num2\n",
    "            else:\n",
    "                return self.add2Num(num2, str(rest), rest = 0)\n",
    "        if num2 == \"\":\n",
    "            if rest == 0:\n",
    "                return num1\n",
    "            else:\n",
    "                return self.add2Num(num1, str(rest), rest = 0)\n",
    "        num = int((int(num1[len(num1)-1]) + int(num2[len(num2)-1]) + rest) % 10)\n",
    "        rest = int((int(num1[len(num1)-1]) + int(num2[len(num2)-1]) + rest) /10)\n",
    "        \n",
    "        # print(rest, num)\n",
    "        return self.add2Num(num1[:len(num1)-1], num2[:len(num2)-1], rest) + str(num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "        lennum1, lennum2 = len(num1), len(num2)\n",
    "        result = [0]*(lennum1+lennum2)\n",
    "\n",
    "        # 共有两层\n",
    "        for i in range(lennum1-1, -1, -1):\n",
    "            for j in range(lennum2-1, -1, -1):\n",
    "                # 首先计算乘积，注意用ASCII码的方式转换为数值\n",
    "                temp = (ord(num1[i])-ord('0'))*(ord(num2[j])-ord('0'))\n",
    "                # 计算所得应和i+j位置求和\n",
    "                _sum = temp+result[i+j+1]\n",
    "                # 第i+j个位置\n",
    "                result[i+j+1] = _sum % 10\n",
    "                # 第i+j-1个位置,此代码为python3，注意使用'//'等号进行运算，例5/2=2.5,5//2=2\n",
    "                result[i+j] += _sum//10\n",
    "        result = [str(i) for i in result]\n",
    "        return ''.join(result[1:]) if result[0] == \"0\" else ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        num1_len, num2_len = len(num1), len(num2)\n",
    "        res = ['0'] * (num1_len + num2_len)\n",
    "        for i in range(num2_len-1, -1, -1):\n",
    "            add = 0\n",
    "            for j in range(num1_len-1, -1, -1):\n",
    "                tmp = int(num1[j]) * int(num2[i]) + add + int(res[i + j + 1])\n",
    "                res[i + j + 1] = str(tmp%10)\n",
    "                add = tmp // 10\n",
    "            res[i] = str(int(res[i])+add)\n",
    "                \n",
    "        for i in range(num1_len + num2_len):\n",
    "            if res[i] != '0':\n",
    "                return ''.join(res[i:])\n",
    "        return '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1==\"0\" or num2==\"0\":\n",
    "            return '0'\n",
    "        new=[0]*(len(num1)+len(num2))\n",
    "        up=[0]*(len(num1)+len(num2))\n",
    "        num1=num1[::-1]\n",
    "        num2=num2[::-1]\n",
    "        for i, s1 in enumerate(num1):\n",
    "            for j,s2 in enumerate(num2):\n",
    "                new[i+j]=int(s1)*int(s2)+new[i+j]\n",
    "                c=new[i+j]//10\n",
    "                new[i+j]=new[i+j]%10\n",
    "                new[i+j+1]+=c\n",
    "        new=new[::-1]\n",
    "        print(new)\n",
    "        i=0\n",
    "        while new[i]==0 and i<len(num1)+len(num2):\n",
    "            i+=1\n",
    "        if i<len(num1)+len(num2):\n",
    "            rs=[str(c) for c in new[i:]]\n",
    "            return \"\".join(rs)\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return str(eval(num1) * eval(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ret = ''\n",
    "        lyst = []\n",
    "        for i in num1[::-1]:\n",
    "            temp = []\n",
    "            add = 0\n",
    "            for j in num2[::-1]:\n",
    "                res = ((ord(i)-48) * (ord(j)-48))+ add\n",
    "                temp.append(res%10)\n",
    "                add = res//10\n",
    "            if add != 0:\n",
    "                temp.append(add)\n",
    "            lyst.append(temp)\n",
    "        sum = 0\n",
    "        print(lyst)\n",
    "        while lyst:\n",
    "            temp = lyst.pop()\n",
    "            sum_temp = 0\n",
    "            while temp:\n",
    "                sum_temp = sum_temp * 10 + temp.pop()\n",
    "            sum = sum*10 + sum_temp\n",
    "        return str(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        dic={\"0\":0,\"1\":1,\"2\":2,\"3\":3,\"4\":4,\"5\":5,\"6\":6,\"7\":7,\"8\":8,\"9\":9}\n",
    "        li = [\"0\",\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"]\n",
    "        res = \"\"\n",
    "        for i in num1:\n",
    "            n1 = n1*10 + dic[i]\n",
    "           \n",
    "        for i in num2:\n",
    "            n2 = n2*10 + dic[i]\n",
    "        res_int = n1*n2\n",
    "        if res_int == 0:\n",
    "            return \"0\"\n",
    "        while res_int!=0:\n",
    "            print(res_int%10)\n",
    "            res = li[res_int%10] + res\n",
    "            res_int = res_int//10\n",
    "       \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        return str(int(num1)*int(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def multiply(self, num1, num2):\n",
    "        \"\"\"\n",
    "        :type num1: str\n",
    "        :type num2: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if num1 == \"0\" or num2 == \"0\": #处理特殊情况\n",
    "            return \"0\"\n",
    "        \n",
    "        l1, l2 = len(num1), len(num2) \n",
    "        if l1 < l2: \n",
    "            num1, num2 = num2, num1 #保障num1始终比num2大\n",
    "            l1, l2 = l2, l1\n",
    "            \n",
    "        num2 = num2[::-1]\n",
    "        res = \"0\"\n",
    "        for i, digit in enumerate(num2):\n",
    "            tmp = self.StringMultiplyDigit(num1, int(digit)) + \"0\" * i #计算num1和num2的当前位的乘积\n",
    "            res = self.StringPlusString(res, tmp) #计算res和tmp的和\n",
    "\n",
    "        return res\n",
    "    \n",
    "    def StringMultiplyDigit(self,string, n):\n",
    "        #这个函数的功能是：计算一个字符串和一个整数的乘积，返回字符串\n",
    "        #举例：输入为 \"123\", 3， 返回\"369\"\n",
    "        s = string[::-1]\n",
    "        res = []\n",
    "        for i, char in enumerate(s):\n",
    "            num = int(char)\n",
    "            res.append(num * n)\n",
    "        res = self.CarrySolver(res)\n",
    "        res = res[::-1]\n",
    "        return \"\".join(str(x) for x in res)\n",
    "        \n",
    "    def CarrySolver(self, nums):  \n",
    "        #这个函数的功能是：将输入的数组中的每一位处理好进位\n",
    "        #举例：输入[15, 27, 12], 返回[5, 8, 4, 1]\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] >= 10:\n",
    "                carrier = nums[i] // 10\n",
    "                if i == len(nums) - 1:\n",
    "                    nums.append(carrier)\n",
    "                else:\n",
    "                    nums[i + 1] += carrier\n",
    "                nums[i] %= 10\n",
    "            i += 1\n",
    "                    \n",
    "        return nums\n",
    "    \n",
    "    def StringPlusString(self, s1, s2):\n",
    "        #这个函数的功能是：计算两个字符串的和。 \n",
    "        #举例：输入为“123”， “456”, 返回为\"579\"\n",
    "        #PS：LeetCode415题就是要写这个函数\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        if l1 < l2:\n",
    "            s1, s2 = s2, s1\n",
    "            l1, l2 = l2, l1\n",
    "        s1 = [int(x) for x in s1]\n",
    "        s2 = [int(x) for x in s2]\n",
    "        s1, s2 = s1[::-1], s2[::-1]\n",
    "        for i, digit in enumerate(s2):\n",
    "            s1[i] += s2[i]\n",
    "            \n",
    "        s1 = self.CarrySolver(s1)\n",
    "        s1 = s1[::-1]\n",
    "        return \"\".join(str(x) for x in s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        # return str(int(num1) * int(num2))\n",
    "\n",
    "        num_dic = {\"0\":0,\"1\":1,\"2\":2,\"3\":3,\"4\":4,\"5\":5,\"6\":6,\"7\":7,\"8\":8,\"9\":9}\n",
    "        num1 = num1[::-1]\n",
    "        num2 = num2[::-1]\n",
    "        add = 0\n",
    "        for index,i in enumerate(num1):\n",
    "            mul = 10 ** index\n",
    "            for j in num2:\n",
    "                add += num_dic[i] * num_dic[j] * mul\n",
    "                mul = mul * 10\n",
    "        \n",
    "        return str(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        res = 0\n",
    "        for i in range(1,len(num1)+1):\n",
    "            for j in range(1, len(num2)+1):\n",
    "                res += int(num1[-i]) * int(num2[-j]) *10**(i+j-2)\n",
    "        return str(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        # 2020/10/11\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "        res = 0\n",
    "        num2=num2[::-1]\n",
    "        num1 = num1[::-1]\n",
    "        for d, i in enumerate(num2):\n",
    "            i = i+'0'*d\n",
    "            tmp = 0\n",
    "            for d2, j in enumerate(num1):\n",
    "                j = j+'0'*d2\n",
    "                tmp += int(i)* int(j)\n",
    "            res += tmp\n",
    "\n",
    "        return str(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        num1 = int(num1)\n",
    "        num2 = int(num2)\n",
    "        \n",
    "        prd = num1*num2\n",
    "\n",
    "        return str(prd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        l1, l2 = len(num1), len(num2)\n",
    "        ans = 0\n",
    "        for i in range(len(num1)-1, -1, -1):\n",
    "            pos1 = l1 - i\n",
    "            carry1 = pow(10, pos1-1)\n",
    "            for j in range(len(num2)-1, -1, -1):\n",
    "                pos2 = l2 - j\n",
    "                carry2 = pow(10, pos2-1)\n",
    "                ans += int(num1[i]) * carry1 * int(num2[j]) * carry2\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        num1 = [int(n) for n in list(num1)[::-1]]\n",
    "        num2 = [int(n) for n in list(num2)[::-1]]\n",
    "        res = [0] * (len(num1) + len(num2))\n",
    "\n",
    "        for i, n1 in enumerate(num1):\n",
    "            for j, n2 in enumerate(num2):\n",
    "                res[i + j] += n1 * n2\n",
    "        \n",
    "        remain = 0\n",
    "        for i,r in enumerate(res):\n",
    "            r += remain\n",
    "            remain = r // 10\n",
    "            res[i] = str(r % 10)\n",
    "        # if remain > 0:\n",
    "        #     res.append(str(remain))\n",
    "        \n",
    "        res = res[::-1]\n",
    "        for i,r in enumerate(res):\n",
    "            if r != '0':\n",
    "                break\n",
    "        res = res[i:]\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        def sign_str(str1: str):\n",
    "            if list(str1)[0] == \"-\":\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        def complete(str1: str, str2: str):\n",
    "            num1, num2 = list(str1), list(str2)\n",
    "            if len(num1) > len(num2):\n",
    "                temp = [\"0\" for _ in range(len(num1)-len(num2))]\n",
    "                temp.extend(num2)\n",
    "                num2 = temp\n",
    "            elif len(num1) < len(num2):\n",
    "                temp = [\"0\" for _ in range(len(num2)-len(num1))]\n",
    "                temp.extend(num1)\n",
    "                num1 = temp\n",
    "            return num1, num2\n",
    "\n",
    "        def divide_conquer(str1: str, str2:str, l: int):\n",
    "            sign = sign_str(str1) * sign_str(str2)\n",
    "            if str1[0] == \"-\":\n",
    "                str1 = str1[1:]\n",
    "            if str2[0] == \"-\":\n",
    "                str2 = str2[1:]\n",
    "            str1, str2 = complete(str1, str2)\n",
    "            l = len(str1)\n",
    "            if l == 1:\n",
    "                if str1[0] == \"0\" or str2[0] == \"0\":\n",
    "                    return 0\n",
    "                else:\n",
    "                    res = int(\"\".join(str1)) * int(\"\".join(str2))\n",
    "                    return sign * res\n",
    "            a = str1[:l//2]\n",
    "            b = str1[l//2:]\n",
    "            c = str2[:l//2]\n",
    "            d = str2[l//2:]\n",
    "            ac = divide_conquer(\"\".join(a), \"\".join(c), len(a))\n",
    "            bd = divide_conquer(\"\".join(b), \"\".join(d), len(b))\n",
    "            abdc = divide_conquer(str(int(\"\".join(a))-int(\"\".join(b))), \\\n",
    "                                  str(int(\"\".join(d))-int(\"\".join(c))), \\\n",
    "                                  len(min(str(int(\"\".join(a))-int(\"\".join(b))), \\\n",
    "                                          str(int(\"\".join(d))-int(\"\".join(c)))))) + \\\n",
    "                   ac + bd\n",
    "            return sign*(ac * pow(10, 2*len(b)) + abdc * pow(10, len(b)) + bd)\n",
    "\n",
    "        return str(divide_conquer(num1, num2, len(num1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "PI = math.pi\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def __FFT_or_IDFT(self, A: List, opt=1) -> List:\n",
    "\n",
    "        if len(A) == 1:\n",
    "            return (A if opt == -1 else A * 2)\n",
    "\n",
    "        lim = len(A)\n",
    "        if opt ==1: lim *= 2\n",
    "        Y = [0] * lim\n",
    "        A0 = A[:: 2]        # [a0, a2, a4 ... ]\n",
    "        A1 = A[1:: 2]       # [a1, a3, a5 ... ]\n",
    "\n",
    "        A0Y = self.__FFT_or_IDFT(A0, opt)\n",
    "        A1Y = self.__FFT_or_IDFT(A1, opt)\n",
    "\n",
    "        theta = 2.0 * PI / lim\n",
    "        wn = complex(math.cos(theta), opt * math.sin(theta))\n",
    "        w = 1\n",
    "        for k in range(lim // 2):\n",
    "            t = w * A1Y[k]\n",
    "            Y[k] = A0Y[k] + t\n",
    "            Y[k + lim // 2] = A0Y[k] - t\n",
    "            w = w * wn\n",
    "\n",
    "        return Y\n",
    "\n",
    "    def FFT(self, A: List) -> List:\n",
    "\n",
    "        return self.__FFT_or_IDFT(A, 1)\n",
    "\n",
    "    def IDFT(self, Y: List) -> List:\n",
    "\n",
    "        A = self.__FFT_or_IDFT(Y, -1)\n",
    "        for i in range(len(A)):\n",
    "            A[i] = int(A[i].real / len(A) + 0.5)\n",
    "\n",
    "        return A\n",
    "\n",
    "    def multiply(self, a: str, b: str) -> str:\n",
    "\n",
    "        if a == \"0\" or b == \"0\":\n",
    "            return \"0\"\n",
    "        if a == \"1\": return b\n",
    "        if b == \"1\": return a\n",
    "\n",
    "        lim = 2 ** math.ceil(math.log2(max(len(a), len(b))))\n",
    "        A = [int(c) for c in a[:: -1]] + [0] * (lim - len(a))\n",
    "        B = [int(c) for c in b[:: -1]] + [0] * (lim - len(b))\n",
    "        assert len(A) == len(B)\n",
    "\n",
    "        AY = self.FFT(A)\n",
    "        BY = self.FFT(B)\n",
    "\n",
    "        CY = [AY[i] * BY[i] for i in range(lim * 2)]\n",
    "        C = self.IDFT(CY)\n",
    "\n",
    "        return self.res(C)\n",
    "\n",
    "    def res(self, A) -> str:\n",
    "        res = \"\"\n",
    "        carry = 0\n",
    "        for ite in A:\n",
    "            x = ite + carry\n",
    "            bt = x % 10\n",
    "            res += str(bt)\n",
    "            carry = x // 10\n",
    "        res = res[:: -1]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            if res[i] != \"0\":\n",
    "                return res[i:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "PI = math.pi\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def __FFT_or_IDFT(self, A: List, opt=1) -> List:\n",
    "\n",
    "        if len(A) == 1:\n",
    "            return (A if opt == -1 else A * 2)\n",
    "\n",
    "        lim = len(A)\n",
    "        if opt ==1: lim *= 2\n",
    "        Y = [0] * lim\n",
    "        A0 = A[:: 2]\n",
    "        A1 = A[1:: 2]\n",
    "\n",
    "        A0Y = self.__FFT_or_IDFT(A0, opt)\n",
    "        A1Y = self.__FFT_or_IDFT(A1, opt)\n",
    "\n",
    "        theta = 2.0 * PI / lim\n",
    "        wn = complex(math.cos(theta), opt * math.sin(theta))\n",
    "        w = 1\n",
    "        for k in range(lim // 2):\n",
    "            t = w * A1Y[k]\n",
    "            Y[k] = A0Y[k] + t\n",
    "            Y[k + lim // 2] = A0Y[k] - t\n",
    "            w = w * wn\n",
    "\n",
    "        return Y\n",
    "\n",
    "    def FFT(self, A: List) -> List:\n",
    "\n",
    "        return self.__FFT_or_IDFT(A, 1)\n",
    "\n",
    "    def IDFT(self, Y: List) -> List:\n",
    "\n",
    "        A = self.__FFT_or_IDFT(Y, -1)\n",
    "        print(A)\n",
    "        for i in range(len(A)):\n",
    "            A[i] = int(A[i].real / len(A) + 0.5)\n",
    "\n",
    "        return A\n",
    "\n",
    "    def multiply(self, a: str, b: str) -> str:\n",
    "\n",
    "        if a == \"0\" or b == \"0\":\n",
    "            return \"0\"\n",
    "        if a == \"1\": return b\n",
    "        if b == \"1\": return a\n",
    "\n",
    "        lim = 2 ** math.ceil(math.log2(max(len(a), len(b))))\n",
    "        A = [int(c) for c in a[:: -1]] + [0] * (lim - len(a))\n",
    "        B = [int(c) for c in b[:: -1]] + [0] * (lim - len(b))\n",
    "        assert len(A) == len(B)\n",
    "\n",
    "        AY = self.FFT(A)\n",
    "        BY = self.FFT(B)\n",
    "\n",
    "        CY = [AY[i] * BY[i] for i in range(lim * 2)]\n",
    "        C = self.IDFT(CY)\n",
    "\n",
    "        return self.res(C)\n",
    "\n",
    "    def res(self, A) -> str:\n",
    "        res = \"\"\n",
    "        carry = 0\n",
    "        for ite in A:\n",
    "            x = ite + carry\n",
    "            bt = x % 10\n",
    "            res += str(bt)\n",
    "            carry = x // 10\n",
    "        res = res[:: -1]\n",
    "        for i in range(len(res)):\n",
    "            if res[i] != \"0\":\n",
    "                return res[i:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        return str(int(num1)*int(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        return str(int(num1)*int(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        f1 = 1\n",
    "        ans = 0\n",
    "        # 倒序遍历\n",
    "        for i in range(len(num1)-1,-1,-1):\n",
    "            # 进位数\n",
    "            f2 = 1\n",
    "            # n1 乘以进位数\n",
    "            n1 = int(num1[i]) * f1\n",
    "\n",
    "            # 倒序遍历\n",
    "            for j in range(len(num2)-1,-1,-1):\n",
    "                n2 = int(num2[j]) * f2   \n",
    "                ans += n1 * n2 \n",
    "\n",
    "                # 进位数处理 *10\n",
    "                f2 *=10\n",
    "            f1 *=10\n",
    "        return str(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        ans1 = 0\n",
    "        ans2 = 0\n",
    "        for i in num1:\n",
    "            ans1 = ans1 * 10 + int(i)\n",
    "        for i in num2:\n",
    "            ans2 = ans2 * 10 + int(i)\n",
    "        \n",
    "        return str(ans1 * ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "        \n",
    "        m, n = len(num1), len(num2)\n",
    "        ans = '0'\n",
    "        for i in range(n-1, -1, -1):\n",
    "            add = 0\n",
    "            y = int(num2[i])\n",
    "            curr = ['0'] * (n-i-1)\n",
    "            for j in range(m-1, -1, -1):\n",
    "                product = y*int(num1[j]) + add\n",
    "                curr.append(str(product % 10))\n",
    "                add = product // 10\n",
    "            if add > 0:\n",
    "                curr.append(str(add))\n",
    "            curr = ''.join(curr[::-1])\n",
    "            ans = self.addString(ans, curr)\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "    def addString(self, num1, num2):\n",
    "        i, j = len(num1)-1, len(num2)-1\n",
    "        add = 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or add != 0:\n",
    "            x = int(num1[i]) if i >= 0 else 0\n",
    "            y = int(num2[j]) if j >= 0 else 0\n",
    "            result = x + y + add\n",
    "            ans.append(str(result%10))\n",
    "            add = result // 10\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        return ''.join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "\n",
    "        if len(num1) < len(num2):\n",
    "            short = num1\n",
    "            long = num2\n",
    "        else:\n",
    "            short = num2\n",
    "            long = num1\n",
    "\n",
    "        # 求 short 乘 1~9 的结果\n",
    "        long = list(map(int, long))\n",
    "        short = list(map(int, short))\n",
    "\n",
    "        # 求 short 乘 long 每个数字的结果，进位\n",
    "        tmp_list = []\n",
    "        mul_dict = {0: [0]}\n",
    "        for i, ones in enumerate(reversed(long)):\n",
    "            if ones not in mul_dict:\n",
    "                mul_res = mul_by_ones(short, ones)\n",
    "                mul_dict[ones] = mul_res\n",
    "            tmp_res = [0] * i + mul_dict[ones]\n",
    "            tmp_list.append(tmp_res)\n",
    "\n",
    "        # 做加法\n",
    "        # add_res = add_list(tmp_list)\n",
    "        add_res = [0]\n",
    "        for l in tmp_list:\n",
    "            add_res = add_two(add_res, l)\n",
    "        add_res.reverse()\n",
    "        add_res = ''.join(map(str, add_res))\n",
    "        return add_res\n",
    "\n",
    "        \n",
    "\n",
    "def add_list(lists):\n",
    "    if len(lists) == 1:\n",
    "        return lists[0]\n",
    "    mid = len(lists) // 2\n",
    "    left = add_list(lists[:mid])\n",
    "    right = add_list(lists[mid:])\n",
    "    res = add_two(left, right)\n",
    "    return res\n",
    "\n",
    "\n",
    "def add_two(left, right):\n",
    "    print(left, right)\n",
    "    res = []\n",
    "    min_len = min(len(left), len(right))\n",
    "    cur_index = 0\n",
    "    tens = 0\n",
    "    while cur_index < min_len:\n",
    "        add_res = left[cur_index] + right[cur_index] + tens\n",
    "        ones = add_res % 10\n",
    "        tens = add_res // 10\n",
    "        res.append(ones)\n",
    "        cur_index += 1\n",
    "\n",
    "    while cur_index < len(left):\n",
    "        add_res = left[cur_index] + tens\n",
    "        ones = add_res % 10\n",
    "        tens = add_res // 10\n",
    "        res.append(ones)\n",
    "        cur_index += 1\n",
    "    while cur_index < len(right):\n",
    "        add_res = right[cur_index] + tens\n",
    "        ones = add_res % 10\n",
    "        tens = add_res // 10\n",
    "        res.append(ones)\n",
    "        cur_index += 1\n",
    "    \n",
    "    if tens > 0:\n",
    "        res.append(tens)\n",
    "    return res\n",
    "\n",
    "\n",
    "def mul_by_ones(num, single):  # reversed\n",
    "    res = []\n",
    "    tens = 0\n",
    "    for digit in reversed(num):\n",
    "        cur_res = digit * single + tens\n",
    "        ones = cur_res % 10\n",
    "        tens = cur_res // 10\n",
    "        res.append(ones)\n",
    "    if tens > 0:\n",
    "        res.append(tens)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        return str(eval(num1)*eval(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        ans=0\n",
    "        for i in range(len(num1)-1,-1,-1):\n",
    "            next1=0\n",
    "            ans1=0\n",
    "            bit1=int(num1[i])\n",
    "            for j in range(len(num2)-1,-1,-1):\n",
    "                bit2=int(num2[j])\n",
    "                sum=bit1*bit2+next1\n",
    "                cur=(sum%10)*(10**(len(num2)-1-j))\n",
    "                next1=int(sum/10)\n",
    "                ans1+=cur\n",
    "            ans1=next1*(10**(len(num2)))+ans1\n",
    "            ans+=ans1*(10**(len(num1)-1-i))\n",
    "        return str(ans)\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1 == '0' or num2 == '0':\n",
    "            return '0'\n",
    "        m, n = len(num1), len(num2)\n",
    "        res = [0 for i in range(m + n)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                x = ord(num1[i]) - ord('0')\n",
    "                y = ord(num2[j]) - ord('0')\n",
    "                res[i + j + 1] += x * y % 10\n",
    "                res[i + j] += x * y // 10\n",
    "        for i in range(m + n - 1, 0, -1):\n",
    "            carry = res[i] // 10\n",
    "            res[i] = res[i] % 10\n",
    "            res[i - 1] += carry\n",
    "        ans = ''.join([str(x) for x in res]).lstrip('0')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        len1, len2 = len(num1), len(num2)\n",
    "        res = [0] * (len1 + len2)  \n",
    "        num1, num2 = num1[::-1],num2[::-1]\n",
    "        for i in range(len1):\n",
    "            for j in range(len2):\n",
    "                mul = int(num1[i]) * int(num2[j])\n",
    "                res[i+j] += mul % 10\n",
    "                if res[i+j] > 9:\n",
    "                    res[i+j+1] += 1\n",
    "                    res[i+j] %= 10 \n",
    "                res[i+j+1] += mul // 10\n",
    "                if res[i+j+1] > 9:\n",
    "                    res[i+j+2] += 1\n",
    "                    res[i+j+1] %= 10 \n",
    "        if res[len1+len2-2] > 9:\n",
    "            res[len1+len2-1] = 1\n",
    "            res[len1+len2-2] %= 10\n",
    "        res = \"\".join([str(c) for c in res[::-1]])\n",
    "        res = res.lstrip(\"0\")\n",
    "        if res == '':\n",
    "            return '0'\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        nums1=num1\n",
    "        nums2=num2\n",
    "        n1=len(nums1)\n",
    "        n2=len(nums2)\n",
    "        out=0\n",
    "        for i in range(n1):\n",
    "            now_1=nums1[n1-i-1]\n",
    "            temp=0\n",
    "            carry_pre=0\n",
    "            for j in range(n2):\n",
    "                now_2=nums2[n2-j-1]\n",
    "                carry=(ord(now_1)-ord('0'))*(ord(now_2)-ord('0'))//10\n",
    "                c=(ord(now_1)-ord('0'))*(ord(now_2)-ord('0'))-10*carry+carry_pre\n",
    "                print(c)\n",
    "                carry_pre=carry+c//10\n",
    "                print(carry_pre)\n",
    "                c=c%10\n",
    "\n",
    "                temp+=c*10**j\n",
    "                #print(temp)\n",
    "            temp=temp+carry_pre*10**(j+1)\n",
    "            \n",
    "            out+=temp*10**i\n",
    "            #print(temp,out)\n",
    "        out=str(out)\n",
    "        return out"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
